package Solution.problem060;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/06/02 13:35
 */
public class BetterSolution {
    public String getPermutation(int n, int k) {
        int[] arr = new int[n];
        for (int i = 1; i <= n; i++) {
            arr[i-1] = i;
        }
        int[] factorials = new int[n+1];
        factorials[0] = 1;
        factorials[1] = 1;
        for (int i = 2; i<=n; i++) {
            factorials[i] = i * factorials[i-1];
        }
        getKthPermutation(arr, k, 0, factorials);
        StringBuilder res = new StringBuilder();
        for (int i : arr) {
            res.append(String.valueOf(i));
        }
        return res.toString();
    }

    private void getKthPermutation(int[] arr, int k, int startIdx, int[] factorials) { // 12, 1, 0
        int n = arr.length - startIdx, // 2
                setSize = factorials[n-1], // 1
                setIdx = k / setSize, // 2
                permIdx = k % setSize; // 0

        if (k == factorials[n]) {
            previousPermutation(arr, 0);
            return;
        }

        if (n == 2) {
            setIdx--;
        }

        // swap
        for (int j = startIdx + 1; j <= startIdx + setIdx; j++) {
            swap(arr, startIdx, j);
        }

        // System.out.println("n = " + n + " setSize = " + setSize + " setIdx = " + setIdx + " permIdx = " + permIdx);
        // System.out.println(Arrays.toString(arr) + " k = " + k + " startIdx = " + startIdx);

        if (n > 2 && permIdx == 0) {
            previousPermutation(arr, startIdx);
            return;
        }

        if (permIdx == 1) {
            return;
        } else if (n > 2 ) {
            getKthPermutation(arr, permIdx, startIdx + 1, factorials); // 5, 1
        }

    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private void previousPermutation(int[] arr, int startIdx) {
        int n = arr.length - startIdx, // 3
                i = arr.length-1; // 2

        while (i > startIdx && arr[i] > arr[i-1]) {
            --i;
        }

        int inversionPoint = i - 1; // 0
        if (inversionPoint == startIdx - 1) {
            i = startIdx;
            int j = arr.length-1;
            while (i < j) {
                swap(arr, i, j);
                ++i; --j;
            }

        } else {
            i = arr.length - 1;
            while (i >= 0 && arr[i] > arr[inversionPoint]) {
                --i;
            }
            swap(arr, i, inversionPoint);
            i = inversionPoint + 1;
            int j = arr.length - 1;
            while (i < j) {
                swap(arr, i, j);
                ++i; --j;
            }
        }


    }
}
